package stack_queue.queue.impl;

import stack_queue.queue.Queue;

import java.util.NoSuchElementException;

/**
 * 基于整型的循环队列
 * @author yuisama
 * @date 2022/01/24 11:48
 **/
public class LoopQueue implements Queue<Integer> {
    private Integer[] data;
    // 指向当前循环队列的队首元素
    private int head;
    // 指向当前循环队列的队尾元素的下一个位置
    private int tail;
    // 当前队列中元素个数(思考:如何仅用tail和head来判断当前队列中的元素个数?)
    private int size;
    // n为希望保存的元素个数
    public LoopQueue(int n) {
        // 在循环队列中浪费一个空间不能存储元素，来判断是否已满
        data = new Integer[n + 1];
    }
    @Override
    public void offer(Integer val) {
        if (isFull()) {
            throw new ArrayIndexOutOfBoundsException("queue is full，cannot offer new val");
        }
        data[tail] = val;
        tail = (tail + 1) % data.length;
        size ++;
    }

    @Override
    public Integer poll() {
        if (isEmpty()) {
            throw new NoSuchElementException("queue is empty!cannot poll");
        }
        Integer val = data[head];
        head = (head + 1) % data.length;
        size --;
        return val;
    }

    @Override
    public Integer peek() {
        if (isEmpty()) {
            throw new NoSuchElementException("queue is empty!cannot peek");
        }
        return data[head];
    }

    @Override
    public boolean isEmpty() {
        return tail == head;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("front [");
        // 取得最后一个元素下标
        int lastIndex = tail == 0 ? data.length - 1 : tail - 1;
        for (int i = head; i != tail;) {
            sb.append(data[i]);
            if (i != lastIndex) {
                sb.append(", ");
            }
            i = (i + 1) % data.length;
        }
        sb.append("] tail");
        return sb.toString();
    }

    public boolean isFull() {
        return (tail + 1) % data.length == head;
    }
}